package it.storm.solution;

/**
 * 1476. 子矩形查询
 * https://leetcode-cn.com/problems/subrectangle-queries/
 */
public class Solutions_1476 {
    public static void main(String[] args) {
        int[][] rectangle = {{1, 2, 1}, {4, 3, 4}, {3, 2, 1}, {1, 1, 1}};
        SubrectangleQueries obj = new SubrectangleQueries(rectangle);
        int res1 = obj.getValue(0, 2);  // output: 1
        System.out.println(res1);
        obj.updateSubrectangle(0, 0, 3, 2, 5);
        int res2 = obj.getValue(0, 2);  // output: 5
        System.out.println(res2);
        int res3 = obj.getValue(3, 1);  // output: 5
        System.out.println(res3);
        obj.updateSubrectangle(3, 0, 3, 2, 10);
        int res4 = obj.getValue(3, 1);  // output: 10
        System.out.println(res4);
        int res5 = obj.getValue(0, 2);  // output: 5
        System.out.println(res5);
    }
}

/**
 * 解法二：历史记录方法（31ms）
 */
class SubrectangleQueries {
    private int[][] rectangle;
    // 历史修改记录数组：arr[0]：记录下第 1 次修改的区域和值
    // arr[0][0] 左上角行、arr[0][1] = 左上角列
    // arr[0][2] 右下角行、arr[0][3] = 右下角列、arr[0][4] = 更新的值
    private int[][] history;
    private int idx;

    public SubrectangleQueries(int[][] rectangle) {
        this.rectangle = rectangle;
        // 最多有 500 次修改
        history = new int[500][5];
        idx = 0;
    }

    public void updateSubrectangle(int row1, int col1, int row2, int col2, int newValue) {
        // 循环更新值
        for (int i = row1; i <= row2; i++) {
            for (int j = col1; j <= col2; j++) {
                rectangle[i][j] = newValue;
            }
        }
    }

    public int getValue(int row, int col) {
        for (int i = idx - 1; i >= 0; i--) {
            int[] cur = history[i];
            if (row >= cur[0] && row <= cur[2] && col >= cur[1] && col <= cur[3]) {
                // [row, col] 区域被修改过，返回被修改后的数据
                return cur[4];
            }
        }
        // [row, col] 区域未修改过，返回最原始的数据
        return rectangle[row][col];
    }
}

/**
 * 解法一：暴力法（32ms）
 */
class SubrectangleQueries1 {
    private int[][] rectangle;

    public SubrectangleQueries1(int[][] rectangle) {
        this.rectangle = rectangle;
    }

    public void updateSubrectangle(int row1, int col1, int row2, int col2, int newValue) {
        // 循环更新值
        for (int i = row1; i <= row2; i++) {
            for (int j = col1; j <= col2; j++) {
                rectangle[i][j] = newValue;
            }
        }
    }

    public int getValue(int row, int col) {
        return rectangle[row][col];
    }
}
